package leetcode.all;


public class Solution629 {

    public static void main(String[] args) {
        System.out.println(kInversePairs(3,1));
    }

    public static int kInversePairs(int n, int k) {
        //动态规划，f[i][j]表示数字1到i的排列中逆序数为j的个数
        //根据数字i在全排列中的下标idx=0到i-1，数字i放在idx那么对逆序数的增加值贡献为i-1-idx（只有i后面的数字才和i构成逆序对）
        // f[i][j] = sum{f[i-1][j-(i-1-0)],f[i-1][j-(i-1-1)],...,f[i-1][j-(i-1-i+1)]}
        // f[i][j-1] = sum{f[i-1][j-1-(i-1-0)],f[i-1][j-1-(i-1-1)],...,f[i-1][j-1-(i-1-i+1)]
        int mod = (int)1e9+7;
        int[][] dp = new int[n + 1][k + 1];
        //初始化
        for (int i = 1; i <= n; i++) {
            dp[i][0] = 1;
        }
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                //为了避免每次都要重复循环计算，dp[i][j] = dp[i][j-1] + dp[i-1][j-(i-1-i+1)] - dp[i-1][j-1-(i-1-0)]
                dp[i][j] = dp[i][j-1] + dp[i-1][j] - (j<i?0:dp[i-1][j-i]);
                if(dp[i][j]>=0) dp[i][j] %= mod;
                else dp[i][j] += mod;
            }
        }
        return dp[n][k];
    }

}
